package com.bm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Description: BM56 有重复项数字的全排列
 *
 * 重复！！
 *
 * @author weiruibai.vendor
 * Date: 2022/9/19 10:39
 */
public class BM56 {

    public static void main(String[] args) {

        int[] num = new int[]{1, 1, 2};
        BM56 bm56 = new BM56();
        System.out.println(bm56.permuteUnique(num));
        System.out.println(bm56.permuteUnique_v1(num));
    }

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        //先按字典序排序
        Arrays.sort(num);
        Boolean[] vis = new Boolean[num.length];
        Arrays.fill(vis, false);
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> temp = new ArrayList<Integer>();
        recursion(res, num, temp, vis);
        return res;
    }

    public void recursion(ArrayList<ArrayList<Integer>> res, int[] num, ArrayList<Integer> temp, Boolean[] vis) {
        //临时数组满了加入输出
        if (temp.size() == num.length) {
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        //遍历所有元素选取一个加入
        for (int i = 0; i < num.length; i++) {
            //如果该元素已经被加入了则不需要再加入了
            if (vis[i])
                continue;
            if (i > 0 && num[i - 1] == num[i] && !vis[i - 1])
                //当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了
                continue;
            //标记为使用过
            vis[i] = true;
            //加入数组
            temp.add(num[i]);
            recursion(res, num, temp, vis);
            //回溯
            vis[i] = false;
            temp.remove(temp.size() - 1);
        }
    }

    public ArrayList<ArrayList<Integer>> permuteUnique_v1(int[] num) {
        Arrays.sort(num);
        HashSet<ArrayList<Integer>> ans = new HashSet<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        process(ans, res, num, new HashSet<>(), new ArrayList<Integer>());
        return res;
    }

    private void process(HashSet<ArrayList<Integer>> ans, ArrayList<ArrayList<Integer>> res, int[] num, Set<Integer> set, ArrayList<Integer> tmpAsn) {
        if (set.size() == num.length) {

            ArrayList<Integer> tmp = new ArrayList<>(tmpAsn);
            if (ans.add(tmp)) {
                res.add(tmp);
            }
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (set.add(i)) {
                tmpAsn.add(num[i]);
                process(ans, res, num, set, tmpAsn);
                tmpAsn.remove(tmpAsn.size() - 1);
                set.remove(i);
            }
        }
    }
}
